/*************************************************************************
 * File Name:    Construct_Binary_Tree_from_Inorder_and_Postorder_Traversal.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013-11-6 11:17:58
 * 
 * Description:  
 |-------------------------------------------------------------------------
 | Problem: Construct Binary Tree from Inorder and Postorder Traversal
 |
 | Given inorder and postorder traversal of a tree, construct the binary tree.
 |
 | Note:
 | You may assume that duplicates do not exist in the tree.
 |-------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
    {
        TreeNode *root;
        dfs(root, inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
        return root;
    }
    
private:
    void dfs(TreeNode* &root, const vector<int> &inorder, int inbeg, int inend, const vector<int> &postorder, int postbeg, int postend)
    {
        if (inbeg > inend) {
            root = NULL;
            return;
        }
        int p;
        
        for (p = inbeg; p <= inend; ++p) {
            if (inorder[p] == postorder[postend]) break;
        }
        root = new TreeNode(postorder[postend]);
        dfs(root->left, inorder, inbeg, p - 1, postorder, postbeg, postbeg + p - inbeg - 1);
        dfs(root->right, inorder, p + 1, inend, postorder, postbeg + p - inbeg, postend - 1);
    }
};

